package offer;

import java.util.Stack;

@FunctionalInterface
public interface KnightProbability {
    double knightProbability(int n, int k, int row, int column);
}
class KnightProbabilityImpl1 implements KnightProbability{

    static final int[][] dirs = new int[][]{{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

    /**
     * 内存溢出
     * @param n
     * @param k
     * @param row
     * @param column
     * @return
     */
    @Override
    public double knightProbability(int n, int k, int row, int column) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{row, column});
        double curProb = 1;
        double ansProb = 1;
        for (int i = 0; i < k; i++) {
            curProb /= 8;
            int stackSize = stack.size();
            for (int j = 0; j < stackSize; j++) {
                int[] curPoint = stack.pop();
                int r = curPoint[0], c = curPoint[1];
                for(int[] dir : dirs){
                    int tempRow = dir[0] + r, tempCol = dir[1] + c;
                    if(tempRow >= 0 && tempRow < n && tempCol >= 0 && tempCol < n){
                        stack.push(new int[]{tempRow,tempCol});
                    }else{
                        ansProb -= curProb;
                    }
                }
            }
        }
        return ansProb;
    }
}
class KnightProbabilityImpl2 implements KnightProbability{
    public static void main(String[] args) {
        new KnightProbabilityImpl2().knightProbability(8,30,6,4);
    }
    static final int[][] dirs = new int[][]{{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

    /**
     * 可能性太多，int和long的精度不够，
     * @param n
     * @param k
     * @param row
     * @param column
     * @return
     */
    @Override
    public double knightProbability(int n, int k, int row, int column) {
        int[][] matrix = new int[n][n];
        int[][] aux_matrix = new int[n][n];
        clearMatrix(matrix);
        clearMatrix(aux_matrix);
        matrix[row][column] = 1;
        for (int iter = 0; iter < k; iter++) {
            clearMatrix(aux_matrix);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for(int[] dir : dirs){
                        int tempRow = dir[0] + i, tempCol = dir[1] + j;
                        if(tempRow >= 0 && tempRow < n && tempCol >= 0 && tempCol < n){
                            aux_matrix[tempRow][tempCol] += matrix[i][j];
                        }
                    }
                }
            }
            // 交换matrix 和 aux_matrix
            int[][] temp = matrix;
            matrix = aux_matrix;
            aux_matrix = temp;
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count += matrix[i][j];
            }
        }
        double baseProb = 1;
        for (int i = 0; i < k; i++) {
            baseProb /= 8;
        }
        return baseProb * count;
    }
    private void clearMatrix(int[][] matrix){
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[i][j] = 0;
            }
        }
    }
}
class KnightProbabilityImpl3 implements KnightProbability{
    public static void main(String[] args) {
        new KnightProbabilityImpl3().knightProbability(8,30,6,4);
    }
    static final int[][] dirs = new int[][]{{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

    /**
     * 时间是o(k*n^2),空间o(n^2),这个实现应该还是有bug的，bug来源于数据精度
     * 当矩阵很大时，每一个矩阵格子上存在的概率很小，由于是浮点数实现，所以最后统计时可能会出现大数吃小数。
     * @param n
     * @param k
     * @param row
     * @param column
     * @return
     */
    @Override
    public double knightProbability(int n, int k, int row, int column) {
        double[][] matrix = new double[n][n];
        double[][] aux_matrix = new double[n][n];
        clearMatrix(matrix);
        clearMatrix(aux_matrix);
        matrix[row][column] = 1;
        for (int iter = 0; iter < k; iter++) {
            clearMatrix(aux_matrix);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for(int[] dir : dirs){
                        int tempRow = dir[0] + i, tempCol = dir[1] + j;
                        if(tempRow >= 0 && tempRow < n && tempCol >= 0 && tempCol < n){
                            aux_matrix[tempRow][tempCol] += matrix[i][j] / 8;
                        }
                    }
                }
            }
            // 交换matrix 和 aux_matrix
            double[][] temp = matrix;
            matrix = aux_matrix;
            aux_matrix = temp;
        }
        double ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans += matrix[i][j];
            }
        }
        return ans;
    }
    private void clearMatrix(double[][] matrix){
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[i][j] = 0;
            }
        }
    }
}